class Solution {
public:
    using ll=long long;
    int n;
    bool check(vector<ll> &power, ll low, int r, int k)
    {
        vector<ll> diff(n+1, 0);
        ll sum_d=0, built=0;
        for(int i=0; i<n; i++) {
            sum_d+=diff[i];
            ll m=low-(power[i]+sum_d); //累加差分值
            if(m<=0) continue;

            //需要在i+r额外建造m个供电站
            built+=m;
            if(built>k) return false;
            
            //区间[i, i+2r]加1
            sum_d+=m;
            diff[min(i+r*2+1, n)]-=m;
        }
        return true;
    }

    long long maxPower(vector<int>& stations, int r, int k) {
        n=stations.size();

        //前缀和
        vector<ll> sum(n+1, 0);
        for(int i=0; i<n; i++) {
            sum[i+1]=sum[i]+stations[i];
        }

        vector<ll> power(n, 0); //初始电量
        ll mn=LLONG_MAX;
        for(int i=0; i<n; i++) {
            power[i]=sum[min(i+r+1, n)]-sum[max(i-r, 0)];
            mn=min(mn, power[i]);
        }

        ll left=mn+k/n, right=mn+k+1;
        while(left+1<right) {
            ll mid=left+(right-left)/2;
            (check(power, mid, r, k)?left:right)=mid;
        }
        return left;

    }
};